// 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。
// 以这种方式修改数组后，返回数组可能的最大和。
// A = [3,-1,0,2], K = 3
// 选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
// 输出：6
// 思路，贪心
// 局部最优，将绝对值大的负数变为正数，如果k大于0，将数值最小的正整数反转

function largestSumAfterKNegations(nums, k) {
    nums.sort((x, y) => Math.abs(y) - Math.abs(x))
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] < 0 && k > 0) {
            k--
            nums[i] = -nums[i]
        }        
    }
    while (k > 0) {
        nums[nums.length - 1] = -nums[nums.length - 1]
        k--
    }
    return nums.reduce((sum, cur) => sum + cur)
}

console.log(largestSumAfterKNegations([3,-1,0,2], 3))